1. The Field of the Invention
The present invention relates to database and file management. Specifically, the present invention relates to methods and systems for updating an inheritance tree of a hierarchical directory tree structure with minimal increase in memory usage, the hierarchical directory tree structure including properties that describe certain nodes within the hierarchical directory structure.
2. The Prior State of the Art
Computer systems typically use a hierarchical directory tree structure for organizing data objects such as files. The following illustrates a conventional hierarchical directory tree structure (hereinafter, xe2x80x9ctreexe2x80x9d) used to store files including xe2x80x9cfile1.logxe2x80x9d through xe2x80x9cfile5.logxe2x80x9d.
In the tree, directories are represented by the entries that end with a forward slash xe2x80x9c/xe2x80x9d while files have no such forward slash. For example, root, dir1 and dir2 are directories and file1.log, file2.log, file3.log, file4.log and file5.log are files. Each directory is followed by an indented list of resources (i.e., files or directories) directly contained by that directory. For example, the root directory xe2x80x9crootxe2x80x9d directly contains directories xe2x80x9cdir1xe2x80x9d and xe2x80x9cdir2xe2x80x9d. The directory xe2x80x9cdir1xe2x80x9d directly contains files xe2x80x9cfile1.logxe2x80x9d, xe2x80x9cfile2.logxe2x80x9d, xe2x80x9cfile3.logxe2x80x9d and xe2x80x9cfile4.logxe2x80x9d. The directory xe2x80x9cdir2xe2x80x9d directly contains file xe2x80x9cfile5.logxe2x80x9d.
Each file and directory represents a xe2x80x9cnodexe2x80x9d in the hierarchical directory tree structure. With the exception of the root directory xe2x80x9crootxe2x80x9d, each node has a xe2x80x9cparentxe2x80x9d node in which the node is directly contained. For example, the parent node of xe2x80x9cdir1xe2x80x9d and xe2x80x9cdir2xe2x80x9d is xe2x80x9crootxe2x80x9d; the parent node of xe2x80x9cfile1.logxe2x80x9d, xe2x80x9cfile2.logxe2x80x9d, xe2x80x9cfile3.logxe2x80x9d and xe2x80x9cfile4.logxe2x80x9d is xe2x80x9cdir1xe2x80x9d; and the parent node of xe2x80x9cfile5.logxe2x80x9d is xe2x80x9cdir2xe2x80x9d. Each directory node may also directly contain xe2x80x9cchildxe2x80x9d nodes. For example, the child nodes of xe2x80x9crootxe2x80x9d are xe2x80x9cdir1xe2x80x9d and xe2x80x9cdir2xe2x80x9d; the child nodes of xe2x80x9cdir1xe2x80x9d are xe2x80x9cfile1.logxe2x80x9d, xe2x80x9cfile2.logxe2x80x9d, xe2x80x9cfile3.logxe2x80x9d and xe2x80x9cfile4.logxe2x80x9d; and the child node of xe2x80x9cdir2xe2x80x9d is xe2x80x9cfile5.logxe2x80x9d.
Each file has an xe2x80x9cancestral linexe2x80x9d proceeding from right to left through the progenitors of the file starting at the file and terminating at the root directory. For example, the ancestral line of xe2x80x9cfile1.logxe2x80x9d proceeds from xe2x80x9cfile1.logxe2x80x9d through xe2x80x9cdir1xe2x80x9d and to xe2x80x9crootxe2x80x9d. The ancestral lines of xe2x80x9cfile2.logxe2x80x9d, file3.logxe2x80x9d and xe2x80x9cfile4.logxe2x80x9d also proceed from the respective file though xe2x80x9cdir1xe2x80x9d and to xe2x80x9crootxe2x80x9d. The ancestral line of xe2x80x9cfile5.logxe2x80x9d proceeds from xe2x80x9cfile5.logxe2x80x9d through xe2x80x9cdir2xe2x80x9d and to xe2x80x9crootxe2x80x9d. This proceeding from child to parent through the ancestral line will be referred to as proceeding xe2x80x9cupxe2x80x9d the ancestral line.
A typical file system might represent a file with its ancestral line. For example, in a file system that uses backslashes, xe2x80x9cfile5.logxe2x80x9d might be represented as xe2x80x9croot dir2 file5.logxe2x80x9d.
Conventional hierarchical directory tree structures may also store property information (sometimes termed xe2x80x9cmetadataxe2x80x9d) that describes the nodes in the tree. For files, this property information might include the content type, title, subject, author, creation date, last edited date and so forth. For directories, this property information might include the content type to be inherited by descendent files, the title, the creation date, the available free space size and so forth.
In the following discussion, the focus will be on a property called a file extension/content type mapping (sometimes termed xe2x80x9cMIMEMAPxe2x80x9d) in which certain file extensions are mapped to certain content types. For example, xe2x80x9cmimemap xe2x80x98.log; text/plainxe2x80x99xe2x80x9d is a mapping property that would indicate that, for the corresponding node, files that have the xe2x80x9c.logxe2x80x9d extension are in plain text format.
For example, the following tree illustrates a conventional hierarchical directory tree structure similar to the above-described tree, but which includes the file extension/content type map xe2x80x9cmimemap: xe2x80x98.log; text/plainxe2x80x99xe2x80x9d for the root directory xe2x80x9croot/xe2x80x9d.
Sometimes a hierarchical directory tree structure follows xe2x80x9cfirst one winsxe2x80x9d inheritance semantics in which property information for a certain directory applies by inheritance to all descendent files and directories contained within the parent directory. However, following xe2x80x9cfirst one winsxe2x80x9d inheritance semantics, the inherited property value can be overwritten for any of the descendent files or directories. In xe2x80x9cfirst one winsxe2x80x9d inheritance semantics, if the property value for a file property is found at the file itself, then that is the property value that applies to the file. If the property value for a file property is not found at the file itself, then one examines the ancestral line of the file to determine the first node that has a property value for the corresponding property proceeding up the ancestral line. The file inherits that first property value found. If there is no property value for the corresponding property at the file or in the ancestral line, then a derived property value is applied to the file from a xe2x80x9cglobalxe2x80x9d location which may be in another branch of the inheritance tree or may be completely outside of the inheritance tree.
In the example tree immediately above, assume that xe2x80x9cfirst one winsxe2x80x9d inheritance semantics are followed. This would means that the mapping of file extensions xe2x80x9c.logxe2x80x9d to the plain text format content type in the root directory xe2x80x9crootxe2x80x9d would apply to all of the descendent files and directories of the root directory. Since none of the descendent files and directories has a mapping property that expresses overwrites the mapping in the root directory, the file extension/content type mapping applies to all of the descendent files and directories within the directory xe2x80x9crootxe2x80x9d. Since all of the files contain the xe2x80x9c.logxe2x80x9d extension, all of the files xe2x80x9cfile1.logxe2x80x9d, xe2x80x9cfile2.logxe2x80x9d, xe2x80x9cfile3.logxe2x80x9d, xe2x80x9cfile4.logxe2x80x9d and xe2x80x9cfile5.logxe2x80x9d are considered plain text files since they inherit the mapping under the xe2x80x9cfirst one winsxe2x80x9d inheritance semantics.
Now suppose that the tree is to be updated. Specifically, a new plain text file called xe2x80x9cfile6.logxe2x80x9d is to be written into xe2x80x9cdir1xe2x80x9d of the tree. Conventional methods would write the file extension/content type mapping directly at the new file xe2x80x9cfile6.logxe2x80x9d as follows.
Suppose that now a HyperText Markup Language (HTML) text file called xe2x80x9cfile7.logxe2x80x9d is written into xe2x80x9cdir1xe2x80x9d of the tree. Conventional methods would write the file extension/content type mapping for that specific file directly at the file as follows.
Note that for every new file written into the tree, the conventional method of updating the tree has written a corresponding file extension/content type mapping property for the file. In trees in which numerous new files are written into the tree, the number of file/extension mapping properties for the tree can become enormous consuming massive quantities of memory space.
Therefore, what is desired are methods and system for updating a hierarchical directory tree structure that follows inheritance semantics while minimizing memory usage.
Methods and systems are described for minimizing increases in memory usage when updating an inheritance tree. An inheritance tree is a parent-child hierarchical directory tree structure that contains files and directory and that also contains property information for some of the files and directories in the tree. In the inheritance tree, property information for a parent directory is inherited by its descendent files and directories. The exception is that the inherited property information is not inherited by a descendent file or directory (or by the descendent""s descendents) that has property information that expressly contradicts the inherited property information.
The inheritance tree is updated by writing new files to the inheritance tree. Each new file may contain a property and a property value. For example, a mapping of file extensions to content types might be a property associate with a file. For instance, the mapping might express that files having the xe2x80x9c.logxe2x80x9d extension are plain text files.
The method determines whether an existing property value that would be applied to the new file matches the property value of the new file. Under xe2x80x9cfirst one winsxe2x80x9d inheritance semantics, an existing property value may be applied to a file by either being 1) set at the file itself, 2) inherited from a node in the ancestral line of the file if the property value is not set at the file itself, or 3) derived from a global location if the value is not set at the file nor at any level in the ancestral line of the file.
For example, if the root directory in the inheritance tree indicated that xe2x80x9c.logxe2x80x9d files are to be interpreted as being plain text files, then this mapping would be inherited by all descendent files and directories in the root directory unless expressly contradicted. However, if a new HTML text file called xe2x80x9cfile.logxe2x80x9d is to be written into the directory, this file would not follow the existing inherited mapping that xe2x80x9c.logxe2x80x9d files are plain text files. That is because the new file xe2x80x9cfile.logxe2x80x9d is not a plain text file, but is an HTML text file despite having the xe2x80x9c.logxe2x80x9d extension. Thus, in this case, the existing property value that would be applied to the new file through inheritance does not match the property value of the new file.
If the method determines that the existing property value does not match the property value of the new file, the property value of the new file is set to be its correct value. This may be accomplished in a number of ways. One way is to set the property information in the ancestral line of the new file. For example, the property value may be set in the ancestral line at the level of the new file itself. In this case, the new file would not incorrectly inherit the existing property value; but instead, the incorrect inherited value is overwritten by the correct value set at the new file. Alternatively, the method may set the new correct value at a progenitor level within the ancestral line. In this alternative, the progenitor level should be a descendent of the level where the existing inherited property value was set. Also, care should be taken not to change any property values of descendent files of the progenitor level.
If the method determines that the existing property value does match the property value of the new file, then the new file is written to the inheritance tree without writing the property information. This is proper since the new file would either correctly inherit the existing property value from one of its progenitors, or the value would be derived for the new file from the global location. In this case, writing the property information for the new file is avoided entirely. Thus, as new files are written to the inheritance tree, the method reduces the amount of property information that needs to be written to the inheritance tree. Thus, the method minimizes increases in memory usage required during updating of the inheritance tree. The conserved memory may then be used for other useful purposes.
In one expansion of this method, the method determines whether or not there is an existing property value at all corresponding to the property for the new file. The above method would then be performed only if there is an existing property value. If there is no existing property value, then the property value for the new file is set so as to reduce the probability that future write requests will result in future property information writes. In one example, this is accomplished by first determining whether or not there is any property information written in the ancestral line of the new file. If so, then the property information for the new file is written in the ancestral line at the level where the other property information was found. If not, then the property information is written at the root location of the virtual server.
Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.